class Solution {
public:
    vector<int> path;
    void dfs(vector<int> &arr, int target, int sum, int ind, vector<vector<int>> &result) {
        if (sum > target) return ;
        if (target == sum) {
            result.push_back(path);
            return ;
        }
        for (int i = ind; i < arr.size(); i++) {
            path.push_back(arr[i]);
            dfs(arr, target, sum + arr[i], i, result);
            path.pop_back();
        }
        return ;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        dfs(candidates, target, 0, 0, result);
        return result;
    }
};
